// 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

// 若可行，输出任意可行的结果。若不可行，返回空字符串。

// 示例 1:

// 输入: S = "aab"
// 输出: "aba"
// 示例 2:

// 输入: S = "aaab"
// 输出: ""
// 注意:

// S 只包含小写字母并且长度在[1, 500]区间内。

#include "stdc++.h"

/* 基于最大堆的贪心算法
*/
class Solution {
public:
    string reorganizeString(string S) {
        if (S.length() < 2) {
            return S;
        }
        vector<int> counts(26, 0);
        int maxCount{0};
        int length = S.length();
        for (int i{0}; i < length; ++i) {
            char c = S[i];
            ++counts[c - 'a'];
            maxCount = max(maxCount, counts[c - 'a']);
        }
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        auto cmp = [&](const char& c1, const char& c2) {
            return counts[c1 - 'a'] < counts[c2 - 'a'];
        };
        priority_queue<char, vector<char>, decltype(cmp)> pq{cmp}; // 大根堆
        for (char c = 'a'; c <= 'z'; ++c) {
            if (counts[c - 'a'] > 0) {
                pq.push(c);
            }
        }
        string res{""};
        while (pq.size() > 1) {
            char c1 = pq.top();
            pq.pop();
            char c2 = pq.top();
            pq.pop();
            res += c1;
            res += c2;
            int index1 = c1 - 'a';
            int index2 = c2 - 'a';
            --counts[index1];
            --counts[index2];
            if (counts[index1] > 0) {
                pq.push(c1);
            }
            if (counts[index2] > 0) {
                pq.push(c2);
            }
        }
        if (pq.size() > 0) {
            res += pq.top();
        }
        return res;
    }
};

/* 基于计数的贪心算法
*/
class Solution {
public:
    string reorganizeString(string S) {
        if (S.length() < 2) {
            return S;
        }
        vector<int> counts(26, 0);
        int maxCount{0};
        int length = S.length();
        for (int i{0}; i < length; ++i) {
            char c = S[i];
            ++counts[c - 'a'];
            maxCount = max(maxCount, counts[c - 'a']);
        }
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        string res(length, ' ');
        int evenIndex{0};
        int oddIndex{1};
        int halfLength = length / 2;
        for (int i{0}; i < 26; ++i) {
            char c = 'a' + i;
            // 先往奇数位上放
            while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) {
                res[oddIndex] = c;
                --counts[i];
                oddIndex += 2;
            }
            //奇数放满了，再往偶数位上放
            while (counts[i] > 0) {
                res[evenIndex] = c;
                --counts[i];
                evenIndex += 2;
            }
        }
        return res;
    }
};